import java.util.*;
public class test {
    //leetcode 230.二叉搜索树中第K小的元素
    class Solution {
        public int num = 0;
        public int cnt = 0;

        public int kthSmallest(TreeNode root, int k) {
            //return dfs(root,k);
            num = k;
            dfs1(root);
            return cnt;
        }
        //未剪枝的方法
        public int dfs(TreeNode root, int k) {
            if(root == null){
                return 0;
            }
            int left = dfs(root.left, k);
            num++;
            if (num == k) {
                return root.val;
            }
            int right = dfs(root.right, k);
            //未剪枝
            return left + right;
        }
        //剪枝的方法
        public void dfs1(TreeNode root){
            if(root == null || num == 0){
                return;
            }
            dfs1(root.left);
            num--;
            if(num == 0){
                cnt = root.val;
            }
            if(num == 0){
                return;
            }
            dfs1(root.right);
        }
    }
    //leetcode 257.二叉树的所有路径
    class Solution {
        public List<String> list = new ArrayList<>();
        public StringBuilder stringbuilder = new StringBuilder();

        public List<String> binaryTreePaths(TreeNode root) {
            // dfs(root);
            String s = new String();
            dfs1(root, s);
            return list;
        }

        // 应用全局变量,"恢复现场"较麻烦
        public void dfs(TreeNode root) {
            if (root == null) {
                return;
            }
            stringbuilder.append(root.val + "->");
            dfs(root.left);
            dfs(root.right);
            int len = stringbuilder.length();
            if (root.left == null && root.right == null) {
                list.add(stringbuilder.substring(0, len - 2));
            }
            int start = len - 4;
            if (root.val < 0)
                start--;
            if (root.val == 100 || root.val == -100)
                start--;
            if (root.val > -10 && root.val < 10)
                start++;
            stringbuilder.delete(start, len);
            return;
        }

        // 不应用全局变量
        public void dfs1(TreeNode root, String s) {
            if (root == null) {
                return;
            }
            s = s + root.val;
            if (root.left != null || root.right != null) {
                s = s + "->";
            }
            dfs1(root.left, s);
            dfs1(root.right, s);
            if (root.left == null && root.right == null) {
                list.add(s);
            }
        }
    }
}
